package com.fr.lintcode;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月22日
*时间：上午11:43:45
*/
public class Q33 {
    /**
     * Get all distinct N-Queen solutions
     * @param n: The number of queens
     * @return: All distinct solutions
     * For example, A string '...Q' shows a queen on forth position
     */
    List<List<String>> rs = new ArrayList<>();

    List<List<String>> solveNQueens(int n) {
        if (n <= 0) {
            return rs;
        }
        // 丨i
        boolean a[] = new boolean[n];
        // 丿x+y
        boolean b[] = new boolean[2 * n];
        // 丶x-y+n
        boolean[] c = new boolean[2 * n];
        List<Integer> result = new ArrayList<>();
        queen(n, 0, a, b, c, result);
        return rs;
    }

    private void queen(int n, int i, boolean a[], boolean b[], boolean[] c, List<Integer> result) {
        List<Integer> l = new ArrayList<>(result);
        if (i >= n) {
            save(n, l);
        } else {
            for (int j = 0; j < n; j++) {
                if (!a[j] && !b[i + j] && !c[i - j + n]) {
                    a[j] = true;
                    b[i + j] = true;
                    c[i - j + n] = true;
                    l.add(j);
                    queen(n, i + 1, a, b, c, l);
                    a[j] = false;
                    b[i + j] = false;
                    c[i - j + n] = false;
                    l.remove((Integer) j);
                }
            }
        }
    }

    private void save(int n, List<Integer> l) {
        char[] c = new char[n];
        for (int i = 0; i < n; i++) {
            c[i] = '.';
        }
        ArrayList<String> list = new ArrayList<>();
        for (int i : l) {
            c[i] = 'Q';
            list.add(new String(c));
            c[i] = '.';
        }
        rs.add(list);
    }

    @Test
    public void testA() {
        List<List<String>> rs = solveNQueens(5);
        int count = 0;
        for (List<String> l : rs) {
            System.out.println(++count + ":");
            System.out.println(l);
        }
    }
}
